Image display nonlinearities cause color shifts and mottle in images mapped to a palette with, conventional mapping algorithms well known in the art. As will hereinafter become clear, a system and method was highly sought for eliminating such artifacts. Accordingly, a technique has been provided by the invention for achieving this object wherein mapping occurs in a space where numbers are linearly related to display lumens. Such linear mapping is made practical in accordance with the invention by a two-step lookup method of finding closest palette colors and by an optimization system and method for deriving such lookup tables.
Referring first to FIG. 1, a prior art nonlinear mapping technique is shown therein. For simplicity, only a single scan line is illustrated. The top illustration depicts a typical output voltage of a digital-to-analog converter (DAC) in a computerized imaging system 13. The middle illustration indicates the lumen values emitted by a typical CRT display driven by system 13 relative to the DAC voltage. The bottom figure illustrates human perception of intensity of the same video information represented in the proceeding two illustrations caused by lumen averaging in the human eye optics. In such systems, simplified for purposes of illustration, there is only provision for white 10, black 14 and 50% gray 12 values in the system's palette (as shown by the ordinate). In the illustrated example, the system is attempting to reproduce an original input which is a constant 50% gray. Accordingly, the system would select a gray value 16 for each pel of the image. Inasmuch as the numbers, corresponding to image pel values utilized by a typical computer in a digital video image processing system, are operated upon by DAC converters, these values may be thought of as representing voltages directly, which explains the labeling of the ordinate as VOLTS. However, when the 50% voltage, corresponding to the gray 12 values 16, are in turn operated upon by a normal nonlinear video monitor, these gray values correspond to 25% lumens. However, physiology of the eye is such that it perceives 25% lumens as being midway between 100% white and 0% black, which is precisely what a camera capturing the original image intended. Television and computer monitors are designed to produce an illumination proportional to the square of the driving voltage. This squaring is another way to state the monitor gamma is 2.0. Halfway through the image conversion, shown at reference numeral 20 in FIG. 1, for illustrative purposes we may assume that in conversion of the image to digital form the 50% gray value 12 from the palette is no longer available. Accordingly, to reproduce gray, the system would therefore have to oscillate between the black and white values to result in the perception of 50% gray. In order to do so the average voltage out of the DAC converters being acted upon by a video monitor would be the same as in the case of utilizing the gray pixel values 16, although in this case alternately pixel values for white 10 and black 14 would have to be selected inasmuch as the gray value is no longer available. This oscillation is shown at reference numeral 21 in FIG. 1.
Although the average voltage value being operated upon by an appropriate video monitor might nevertheless be the same, something quite different happens from the situation first depicted with reference to the portion 23 of FIG. 1. The video amplifier of the display monitor would typically oscillate as each white or black pixel is displayed between 100% white and 0% black lumens However due to numerous physical phenomenon such as electrons blurring linearly on their way to the phosphor of the display or photons blurring on their way to the retina, etc., the human eye would nevertheless finally perceive 50% lumens as shown at reference numeral 22 (e.g., a value twice the intended 25% lumens shown at reference numeral 18).
Referring now to FIG. 2, again for illustrative purposes, one might imagine a revised mapping program working with numbers representing not voltage but rather lumens in accordance with the invention, which more desirably would provide for image mapping in linear space. The original input signal must be converted from volts to lumens, and the palette colors in like manner would be translated to lumens. In such a case, the original input 16 shown in FIG. 1 would thereby be represented in the computer system 13 as a constant 25% lumens shown at reference numeral 24 of FIG. 2, and the colors in the palette would be black, white and 25% lumens gray.
In terms of the display 33, at first, the gray values 30 would be selected as perfect matches for each pel. At a midway point 26, for illustrative purposes similar to the midway point 20 of FIG. 1, midway through the conversion one might again assume that the gray level was removed from the palette and if so, again something quite different occurs. The video processing system 13 would aim at 25% lumens and not 50% to as before, therefore choosing only half as many white pels 28 as it did previously in the case of the example of FIG. 1. Accordingly, the eye would thus perceive the desired 25% lumens as shown at reference numeral 35 and not the jump to the 50% lumens as in the prior example relative to FIG. 1. In other words from the foregoing, it will be apparent that the loss of the gray pel values would not make the image appear twice as bright as it should, be.
Although the foregoing examples are rather simplistic and extreme, the effect discovered may often in like manner be equally as pronounced. In actual use, however, more commonly the perceived effect is more subtle but, nevertheless, does lighten and add mottle in excess of diffusion noise in proportion to the square of the magnitude of the diffused error. In most conventional palettes there are fewer colors along the blue axis, and therefore more diffused error along the blue axis, thereby explaining the bluishness often seen in some mapped images. Particularly in high noise diffusion systems such as those hereinafter discussed referring to separated luminance and chrominance diffusion and positive feedback error diffusion, image mapping calculated in linear lumen space as portrayed in FIG. 2 is necessary to prevent very noticeable color shifts and mottle.
The assumption has been made in the foregoing that the highest frequencies, in fact, get transmitted through the video amplifier of the display to the electron gun. If the signal at this point is peaked to overcome blurring by the display tube, then the effect hereinbefore noted may be magnified, whereas if the video amplifier is sluggish the effect is less pronounced. The nonlinearity occurs in the electron gun of the cathode ray tube (CRT). Blurring caused by spread of the electron beam, phosphor light piping and blurring by the eye lens are all linear, and thus overall system resolution is not a measure of the effect.
In provision for an algorithm to perform mapping in the manner described with reference to FIGS. 1 and 2, as hereinbefore noted such mapping might be similar after input and palette conversion. However, as depicted in FIG. 3, a quantization or granularity problem is associated with linear mapping. As shown at reference numeral 40, an original signal would have states spaced nonlinearly when plotted on a linear lumens scale, such as the 16 states shown depicted therein graphically. Although these states are nonlinear, they nevertheless represent equal steps of perception, and thus all states are equally important.
In contrast, if a linear lumen scale is selected, 42, capable of resolving original nonlinear input as, for example, in shadows, then the linear representation must have 224 states shown at reference numeral 41 to match just 16 states of input shown at reference numeral 40. However, there are even further difficulties with such linear representations. When an input has more than 16 states, which as a practical matter would be anticipated, one would require even more resolution to avoid roundoff, and signals must further be represented far beyond saturation, particularly with high performance mapping algorithms which can drift far into saturation on the color axis. The three linear color coordinates must each be 16-bit words, and even that can be marginal. With the advent of modern computing power, 16-bit arithmetic poses no real problem in image processing. However, in order to find the closest palette color to a specific aim color, even with 16-bit arithmetic, this objective can in fact pose extreme problems addressed by the subject invention. A direct search algorithm, for example, may require many hours in order to map an image. In some prior art methods, such as represented in the Audio Visual Connection product of the IBM Corporation, a table lookup method is employed to locate the closest palette color. However concatenating three 16-bit integers yields a pointer into a table which is impractically large.
For purposes of background, the subject invention employs a two-stage lookup as illustrated in FIG. 4. First, each of three 16-bit color vectors 42-46 are employed to point to its own lookup table to select one of approximately 50 very strategically placed states. The results of these three lookups may be combined to form a single pointer into a large three-dimensional lookup table that holds the closest palette colors in the manner of the invention to be hereinafter described in greater detail. Lookup tables have been well known and employed in the video image processing field for several years. However, as just described, a method was needed in the art for image mapping in linear space to reduce or eliminate artifacts caused by image display nonlinearities employing linear mapping wherein a practical lookup method of finding closest palette colors could be provided and wherein placement of states is optimized in order to achieve such practicality.